package Tree;

public class Test {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    public class Solution {
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null){
                return pRootOfTree;
            }
            TreeNode cur = pRootOfTree;
            TreeNode prev = null;
            TreeNode root = null;
            while (cur!=null){
                prev = cur;
                cur = cur.left;
            }
            root = cur;
            cur.right = prev;
            cur = pRootOfTree.left;
            while (cur!=null){
                prev = cur;
                cur = cur.right;
            }
            cur.right = pRootOfTree;
            cur.left = prev;
            while (cur!=null){
                prev = cur;
                cur = cur.right;
            }
            cur.left = prev;
            cur = pRootOfTree.right;
            while (cur!=null){
                prev = cur;
                cur = cur.left;
            }
            cur.left = pRootOfTree;
            cur.right = prev;


            return root;
        }
    }

    public static void main1(String[] args) {
        //测试两棵树是否相同
        BinaryTree tree = new BinaryTree();
        BinaryTree.TreeNode root1 = tree.createTree();
        BinaryTree.TreeNode root2 = tree.createTree();

        System.out.println(tree.isSameTree(root1, root2));
    }
}
